1730C - Minimum Notation - CodeForces Solution

import os
import sys
import math
from io import BytesIO, IOBase
from collections import deque,defaultdict,OrderedDict,Counter
from heapq import heappush,heappop,heapify
from bisect import bisect_right,insort,bisect_left
from functools import lru_cache
from itertools import permutations,combinations

sys.setrecursionlimit(10**6)

def STRIN():return input()
def INTIN():return int(input())
def LINT():return list(map(int,input().split()))
def LSTR():return list(map(str,input().split()))
def MINT():return map(int,input().split())
def MSTR():return map(str,input().split())

def divisors(n) :
     
    c=0
    i=1
    while i <= int(math.sqrt(n)):
         
        if (n % i == 0) :
            if (n // i == i):
                c+=1
            else :
                c+=2
                 
        i = i + 1

    return c 

def isValid(x,y,n,m,graph,vis):
    if x<0 or x>=n or y<0 or y>=m or graph[x][y]=='#' or vis[x][y]:

        return False

    return True


def dfs(u,graph,vis,parent,p,vertex):
    
    vis[u]=1
   
    parent[u]=p
    for v in graph[u]:
       
        if vis[v]:
            if p!=v:
                vertex[0]=v 
                vertex[1]=u
                return True
 
        if not vis[v]:
            
            if dfs(v,graph,vis,parent,u,vertex):                               
                return True
    
    return False
 

def bfs(u,graph,vis,teams):
    pass

    
def palin(s):
    s=str(s)

    i=0
    j=len(s)-1

    while i<=j:
        if s[i]!=s[j]:
            return False

        i+=1
        j-=1


    return True




def solve():
    
    s=STRIN()
    s=list(s)
    ans=[0]*len(s)
    dic=defaultdict(list)

    for i,j in enumerate(s):
        dic[j].append(i)

    
    for j,i in enumerate(s):

        temp=int(i)
        temp-=1
        
        while temp>=0:
            
            if str(temp) in dic:
                l=dic[str(temp)]
                x=bisect_right(l,j)
                
                if x<len(l):
                    
                    s[j]=str(min(int(i)+1,9))

                    break

            temp-=1


    print(''.join(sorted(s)))




    











    

    
    
def main():
    ans=[]
    letter='abcdefghijklmnopqrstuvwxyz'
    
    for i in letter:
        ans.append(i)

    for i in letter:
        for j in letter:
            ans.append(i + j)
            
    for i in letter:
        for j in letter:
            for k in letter:
                ans.append(i + j + k)

    ans={}
    k=1
    for i in range(97,124):
        ans[str(k)]=chr(i)
        k+=1

    for _ in range(INTIN()):
        solve()
    
    
        






BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")


if __name__ == "__main__":
    main()